package org.algorithm.熊猫.链表;

import org.algorithm.biubiu.wheel_1.common.ListNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2022/2/25
 * @Link {https://leetcode-cn.com/problems/next-greater-node-in-linked-list/}
 */
public class 链表中下一个最大的节点 {


    @Test
    public void test() {
        int[] ints = nextLargerNodes(ListNode.build(1, 7, 5, 1, 9, 2, 5, 1));
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i]);
        }
    }

    /**
     *  垃圾解法。
     * @param head
     * @return
     */
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> arr = new ArrayList<>();
        ListNode curtNode = head;
        while (curtNode != null) {
            int val = curtNode.val;
            arr.add(0);

            ListNode lin = curtNode.next;
            while (lin != null) {
                if (lin.val > val) {
                    arr.remove(arr.size() - 1);
                    arr.add(lin.val);
                    break;
                }
                lin = lin.next;

            }
            curtNode = curtNode.next;
        }
        int[] result = new int[arr.size()];
        for (int i = 0; i < arr.size(); i++) {
            result[i] = arr.get(i);
        }
        return result;
    }
}
